package cn.corffen.test.algorithm.leetcode.easy;

import com.corffen.libsource.TreeNode;

import java.util.*;

public class EasyLeet {

    public static void main(String[] args) {

//        printRoman();
//        printMergerTwoList();

//        printCountAndSay();
//        printAddBinary();

//        printSqrt();

//        printRemoveDuplicateListNode();

//        printMergeTwoArray();
        printTriangle2();
    }

    private static void printTriangle() {
        List<List<Integer>> generate = generate(5);
        System.out.println(Arrays.deepToString(generate.toArray()));
    }

    private static void printTriangle2() {
        List<List<Integer>> generate = generate(5);
        System.out.println(Arrays.deepToString(generate.toArray()));

        for (int i = 1; i < 6; i++) {
            List<Integer> rows = getRow(i);
            System.out.println(Arrays.toString(rows.toArray()));
        }
    }

    private static void printMergeTwoArray() {
        int[] number1 = new int[10];
        for (int i = 0; i < 5; i++) {
            number1[i] = i + 1;
        }

        int[] number2 = new int[4];
        for (int i = 0; i < 3; i++) {
            number2[i] = i + 2;
        }
        mergerTwoArray(number1, 5, number2, 3);
        System.out.println(Arrays.toString(number1));
    }

    private static void printRemoveDuplicateListNode() {
        ListNode head = new ListNode(0);
        ListNode current = head;
        for (int i = 0; i < 5; i++) {
            current.next = new ListNode(i >= 3 ? i - 1 : i);
            current = current.next;
        }
        System.out.println(head.toString());
        System.out.println("去除重复的值后:" + removeDuplicates(head).toString());
    }

    private static void printSqrt() {
        int[] numbers = new int[]{4, 8, 9, 17, 38, 50};
        for (int i = 0; i < numbers.length; i++) {
            System.out.println(numbers[i] + " 的算数平方跟为:" + mySqrt(numbers[i]));
        }
    }

    private static void printAddBinary() {
        String a = "101";
        String b = "1111";
        System.out.println(a + "+" + b + "=" + addBinary(a, b));
    }

    private static void printCountAndSay() {
        for (int i = 1; i < 31; i++) {
            System.out.println(i + ":" + countAndSay(i));
        }
    }

    private static void printMergerTwoList() {
        ListNode l10 = new ListNode(1);
        ListNode l11 = new ListNode(2);
        ListNode l12 = new ListNode(3);
        ListNode l13 = new ListNode(34);
        l10.next = l11;
        l11.next = l12;
        l12.next = l13;


        ListNode l20 = new ListNode(21);
        ListNode l21 = new ListNode(22);
        ListNode l22 = new ListNode(23);
        ListNode l23 = new ListNode(44);

        l20.next = l21;
        l21.next = l22;
        l22.next = l23;
        System.out.println("node1=" + l10);
        System.out.println("node2=" + l20);
        ListNode result = mergerTwoList(l10, l20);
        System.out.println("合并后:" + result);
    }

    private static void printRoman() {
        String[] strings = new String[]{"III", "IV", "IX", "LVIII", "MCMXCIV"};
        for (int i = 0; i < strings.length; i++) {
            System.out.println(strings[i] + " =" + romanToInt(strings[i]));
        }
    }

    /**
     * 判断一个整数是否为回文数
     * 思路: 反转一个整数 当不断地除以10 > 反转数时,直到不再大于就结束
     * 此时的数值与反转的数 如果相等,表示是回文数
     * 或者 x如果是奇数位,那么需要反转的结果在除以10 与此时的x相等也为回文数.
     *
     * @param x
     * @return
     */
    public static boolean isPalindrome(int x) {
        if (x < 0 || (x != 0 && x % 10 == 0)) {
            return false;
        }
        int halfReverse = 0;
        while (x > halfReverse) {
            halfReverse = 10 * halfReverse + x % 10;
            x /= 10;
        }
        return x == halfReverse || halfReverse / 10 == x;
    }

    /**
     * 罗马数字字符串转成int
     * 从最后一位开始,如果前一位比相邻的后一位小,就将其结果减去前一位这个值.
     * 否则就累加当前的值.
     * 最终返回转换后的结果
     *
     * @param s
     * @return
     */
    public static int romanToInt(String s) {
        if (s == null || s.length() < 1) {
            return 0;
        }
        Map<Character, Integer> map = new HashMap<>();
        map.put('I', 1);
        map.put('V', 5);
        map.put('X', 10);
        map.put('L', 50);
        map.put('C', 100);
        map.put('D', 500);
        map.put('M', 1000);
        int len = s.length();
        int sum = map.get(s.charAt(len - 1));
        for (int i = len - 2; i >= 0; i--) {
            if (map.get(s.charAt(i)) < map.get(s.charAt(i + 1))) {
                sum -= map.get(s.charAt(i));
            } else {
                sum += map.get(s.charAt(i));
            }
        }
        return sum;
    }

    public static String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        int min = Integer.MAX_VALUE;
        for (String str : strs) {
            min = Math.min(min, str.length());
        }

        for (int i = 0; i < min; i++) {
            for (int j = 1; j < strs.length; j++) {
                if (strs[0].charAt(i) != strs[j].charAt(i)) {
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0].substring(0, min);
    }

    /**
     * 如果是左边的括号就入栈
     * 如果是右边的括号就出栈并比较当前出栈的是否与之对应,如果不匹配,直接返回false
     *
     * @param s
     * @return
     */
    public static boolean isValid(String s) {
        char[] stack = new char[s.length() + 1];
        int top = 1;
        for (char c : s.toCharArray()) {
            if ('(' == c || '{' == c || '[' == c) {
                stack[top++] = c;
            } else if (')' == c && stack[--top] != '(') {
                return false;
            } else if ('}' == c && stack[--top] != '{') {
                return false;
            } else if (']' == c && stack[--top] != '[') {
                return false;
            }
        }
        return top == 1;
    }

    public static ListNode mergerTwoList(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode tmp = head;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                tmp.next = l1;
                l1 = l1.next;
            } else {
                tmp.next = l2;
                l2 = l2.next;
            }
            tmp = tmp.next;
        }
        tmp.next = l1 != null ? l1 : l2;
        return head.next;
    }

    /**
     * 去除有序的数组中重复的元素
     * 思路:
     * tail指向数组的末端.
     * 注意因为是有序的数组,所以只需要比较相邻的元素
     * 遍历数组,如果前一项与后一项不相等.就赋值当前值给tail对应的值,并将tail索引加1
     *
     * @param numbers 给定的数组
     * @return 数组的长度
     */
    public static int removeDuplicates(int[] numbers) {
        int len = numbers.length;
        if (len < 1) {
            return len;
        }
        int tail = 1;
        for (int i = 1; i < len; i++) {
            if (numbers[i - 1] < numbers[i]) {
                numbers[tail++] = numbers[i];
            }
        }
        return tail;
    }

    /**
     * 删除数组中指定的元素
     * 思路:
     * 用一个指针指向数组的开头,遍历数组,如果当前值与指定值不相等
     * 就将指针向后移动,并把当前的值赋给该指针对应的索引值.
     *
     * @param numbers 指定的数组
     * @param val     指定要删除的数
     * @return 返回删除数组中指定元素后的长度
     */
    public static int removeElement(int[] numbers, int val) {
        int tail = 0;
        for (int i = 0, n = numbers.length; i < n; i++) {
            if (numbers[i] != val) {
                numbers[tail++] = numbers[i];
            }
        }
        return tail;
    }

    /**
     * 查找子字符串在主字符串中的位置
     * 思路: 暴力匹配.对于较短的字符串速度还是挺快的
     * 用指针i指向主字符串
     * 指针j指向子字符串.
     * 同时移动两个指针进行比较,如果不相等,就重置指针j从0开始,并将i向后移动
     * 在依次比较两个字符.
     * 如果碰到当前的j指针与子字符串的长度相等,说明找到了.返回当前的i即可.
     *
     * @param haystack
     * @param needle
     * @return
     */
    public static int indexOf(String haystack, String needle) {
        int l1 = haystack.length();
        int l2 = needle.length();
        if (l1 < l2) {
            return -1;
        }

        for (int i = 0; ; i++) {
            if (i + l2 > l1) {
                return -1;
            }
            for (int j = 0; ; j++) {
                if (j == l2) {
                    return i;
                }
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    break;
                }
            }
        }
    }

    /**
     * 从一个没有重复元素的已排序数组中找到插入位置的索引.
     *
     * @param numbers
     * @param target
     * @return
     */
    public static int searchInsert(int[] numbers, int target) {
        int lo = 0;
        int hi = numbers.length - 1;
        int mid = lo + (hi - lo) / 2;
        while (lo <= hi) {
            if (numbers[mid] >= target) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
            mid = lo + (hi - lo) / 2;
        }
        return lo;
    }

    /**
     * 38.「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。前五项如下：
     * <p>
     * 1.     1
     * 2.     11
     * 3.     21
     * 4.     1211
     * 5.     111221
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/count-and-say
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param n
     * @return
     */
    public static String countAndSay(int n) {
        String str = "1";
        while (--n > 0) {
            int times = 1;
            int len = str.length();
            StringBuilder sb = new StringBuilder();
            for (int i = 1; i < len; i++) {
                if (str.charAt(i - 1) == str.charAt(i)) {
                    times++;
                } else {
                    sb.append(times).append(str.charAt(i - 1));
                    times = 1;
                }
            }
            str = sb.append(times).append(str.charAt(len - 1)).toString();
        }
        return str;
    }

    /**
     * 从一个只包含大小字母和空格字符的字符串中得到最后一个单词的长度
     *
     * @param s
     * @return
     */
    public static int lengthOfLastWord(String s) {
        int p = s.length() - 1;
        while (p >= 0 && s.charAt(p) == ' ') {
            p--;
        }
        int end = p;
        while (p >= 0 && s.charAt(p) != ' ') {
            p--;
        }
        return end - p;
    }

    public static int[] plusOne(int[] a) {
        int length = a.length - 1;
        for (int i = length; i >= 0; i--) {
            a[i]++;
            a[i] %= 10;
            if (a[i] != 0) {
                return a;
            }
        }
        int[] result = new int[length + 2];
        result[0] = 1;
        return result;
    }

    /**
     * 67.两个二进制的字符串相加得到一个新的二进制字符串
     * 思路:
     * 从最后一位开始相加.每次将结果carry(有0,1,2三个值) %2之后 (要么为0,要么为1)插入到前面
     * 然后对carry /2 因为该值如果为2,就会往前进一.否则就从0开始相加
     *
     * @param a
     * @param b
     * @return
     */
    public static String addBinary(String a, String b) {
        int p1 = a.length() - 1;
        int p2 = b.length() - 1;
        int carry = 0;
        StringBuilder sb = new StringBuilder();
        while (p1 >= 0 && p2 >= 0) {
            carry += a.charAt(p1--) - '0';
            carry += b.charAt(p2--) - '0';
            sb.insert(0, (char) (carry % 2 + '0'));
            carry >>= 1;
        }
        while (p1 >= 0) {
            carry += a.charAt(p1--) - '0';
            sb.insert(0, (char) (carry % 2 + '0'));
            carry >>= 1;
        }
        while (p2 >= 0) {
            carry += a.charAt(p2--) - '0';
            sb.insert(0, (char) (carry % 2 + '0'));
            carry >>= 1;
        }
        if (carry == 1) {
            sb.insert(0, '1');
        }
        return sb.toString();
    }

    /**
     * 牛顿迭代法
     * 令第k+1项为y
     * 第k项为x
     * 有:y  = (x + n/x)/2;
     *
     * @param x
     * @return
     */
    public static int mySqrt(int x) {
        long n = x;
        while (n * n > x) {
            n = (n + x / n) / 2;
        }
        return (int) n;
    }

    /**
     * 删除有序链表中重复的元素
     *
     * @param head
     * @return
     */
    public static ListNode removeDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode current = head;
        while (current.next != null) {
            if (current.next.val == current.val) {
                current.next = current.next.next;
            } else {
                current = current.next;
            }
        }
        return head;
    }

    /**
     * 将有序数组number2合并到有序数组number1中
     * 使之成为一个新的有序数组.
     *
     * @param numbers1 有序数组1 容量足够大
     * @param m        number1有效元素的个数
     * @param number2  number2
     * @param n        number2有效元素的个数
     */
    public static void mergerTwoArray(int[] numbers1, int m, int[] number2, int n) {
        int p = m-- + n-- - 1;
        while (m >= 0 && n >= 0) {
            numbers1[p--] = numbers1[m] > number2[n] ? numbers1[m--] : number2[n--];
        }
        while (n >= 0) {
            numbers1[p--] = number2[n--];
        }
    }

    public static List<List<Integer>> generate(int numRows) {
        List<List<Integer>> triangle = new ArrayList<>();
        if (numRows <= 0) {
            return triangle;
        }
        triangle.add(new ArrayList<>());
        triangle.get(0).add(1);
        for (int i = 1; i < numRows; i++) {
            List<Integer> row = new ArrayList<>();
            List<Integer> preRow = triangle.get(i - 1);

            row.add(1);
            for (int j = 1; j < i; j++) {
                row.add(preRow.get(j - 1) + preRow.get(j));
            }
            row.add(1);
            triangle.add(row);
        }
        return triangle;
    }

    public static List<Integer> getRow(int rowIndex) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < rowIndex; ++i) {
            //最后一位是1
            res.add(1);
            //从倒数第二项开始,直到第一项.
            for (int j = i - 1; j > 0; --j) {
                res.set(j, res.get(j - 1) + res.get(j));
            }
        }
        return res;
    }

    private static int max = 0;
    public static int diameterOfBinaryTree(TreeNode root) {
        helper(root);
        return max;
    }

    private static int helper(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = helper(root.left);
        int right = helper(root.right);
        max = Math.max(max, left + right);
        return Math.max(left, right) + 1;
    }

    /**
     * 给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
     *
     * 示例 1:
     *
     * 输入: "Let's take LeetCode contest"
     * 输出: "s'teL ekat edoCteeL tsetnoc" 
     *
     * 作者：力扣 (LeetCode)
     * 链接：https://leetcode-cn.com/leetbook/read/array-and-string/c8su7/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    public String reverseWords(String s) {
        String[] strings = s.split("\\s+");
        List<String> ans = new ArrayList<>();
        for (String string : strings) {
            ans.add(reverse(string));
        }
        return String.join(" ", ans);
    }

    public String reverse(String s){
        int length = s.length();
        int lo = 0;
        int hi = length-1;
        char[] chars = s.toCharArray();
        while (lo < hi) {
            char temp = chars[lo];
            chars[lo] = chars[hi];
            chars[hi] = temp;
            lo++;
            hi--;
        }
        StringBuilder sb = new StringBuilder();
        for (char c : chars) {
            sb.append(c);
        }
        return sb.toString();
    }

    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i - 1]) {
                return nums[i];
            }
        }
        return nums[0];
    }

    public int findMin2(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int lo = 0;
        int hi = nums.length-1;
        if (nums[hi] > nums[0]) {
            return nums[0];
        }
        while (hi >= lo) {
            int mid = lo + (hi-lo)/2;
            if (nums[mid] > nums[mid + 1]) {
                return mid+1;
            }
            if (nums[mid - 1] > nums[mid]) {
                return mid;
            }

            if (nums[mid] > nums[0]) {
                lo = mid+1;
            }else {
                hi = mid-1;
            }
        }
        return -1;
    }
    public int majorityElement(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (map.containsKey(nums[i])) {
                int count = map.get(nums[i]);
                map.put(nums[i], ++count);
                if (count > n / 2) {
                    return nums[i];
                }else {
                    map.put(nums[i],1);
                }
            }
        }
        return -1;
    }
}
